package practice;

import java.util.*;

public class Day33 {
    //字符串解码
    public String decodeString(String s) {
        Stack<Character> stack = new Stack<>();
        int i = 0;
        while (i < s.length()) {
            char ch = s.charAt(i);
            if (ch != ']') {
                stack.push(ch);
            } else {
                //一直出到数字
                StringBuilder str = new StringBuilder();
                while (!stack.isEmpty() && !Character.isDigit(stack.peek())) {
                    char c = stack.pop();
                    if (c != '[') {
                        str.append(c);
                    }
                }
                //出数字部分
                int sum = 0;
                //有可能出现十位数，百位数
                int k = 0;
                while (!stack.isEmpty() && Character.isDigit(stack.peek())) {
                    char c = stack.pop();
                    sum += Math.pow(10, k++) * (c - '0');
                }
                str = str.reverse();
                //放到字符串中
                for (int a = 0; a < sum; a++) {
                    for (int j = 0; j < str.length(); j++) {
                        stack.push(str.toString().charAt(j));
                    }
                }
            }
            i++;
        }
        StringBuilder ret = new StringBuilder();
        while (!stack.isEmpty()) {
            ret.append(stack.pop());
        }
        return ret.reverse().toString();
    }

    //字符串乘法
    public String multiply(String num1, String num2) {
        if(num1.equals("0") || num2.equals("0")) {
            return "0";
        }
        int n1 = num1.length();
        int n2 = num2.length();
        int[] hash = new int[n1+n2-1];
        for(int i = n1-1; i >= 0; i--) {
            char c1 = num1.charAt(i);
            for(int j = n2-1; j >= 0; j--) {
                char c2 = num2.charAt(j);
                hash[i+j] += ((c1-'0') * (c2-'0'));
            }
        }
        //从数组最后一个元素向前进位相加
        int n = hash.length;
        StringBuilder ret = new StringBuilder();
        //存储进位
        int k = 0;
        for(int i = n-1; i >= 0; i--) {
            ret.append((hash[i]+k) % 10);
            k = (hash[i]+k) / 10;
        }
        if(k != 0) {
            ret.append(k);
        }
        return ret.reverse().toString();
    }
    //腐烂的橘子
    private int[] dx = { 0, 0, 1, -1 };
    private int[] dy = { 1, -1, 0, 0 };

    public int orangesRotting(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        int ret = 0;
        int num = 0;
        Queue<int[]> stack = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    num++;
                } else if (grid[i][j] == 2) {
                    stack.offer(new int[] { i, j });
                }
            }
        }
        while (num > 0 && !stack.isEmpty()) {
            ret++;
            int size = stack.size();
            while (size != 0) {
                int[] top = stack.poll();
                for (int k = 0; k < 4; k++) {
                    int x = top[0] + dx[k];
                    int y = top[1] + dy[k];
                    if (x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == 1) {
                        grid[x][y] = 2;
                        num--;
                        stack.offer(new int[] { x, y });
                    }
                }
                size--;
            }
        }

        return num == 0 ? ret : -1;
    }
    //课程表
    public boolean canFinish(int numCourses, int[][] p) {
        int[] in = new int[numCourses];
        int n = p.length;
        //统计入度
        Stack<Integer> s = new Stack<>();
        for(int i = 0; i < n; i++) {
            in[p[i][0]]++;
        }
        //建图
        Map<Integer, List<Integer>> map = new HashMap<>();
        for(int i = 0; i < n; i++) {
            if(map.getOrDefault(p[i][1],null) == null) {
                map.put(p[i][1],new ArrayList<>());
            }
            map.get(p[i][1]).add(p[i][0]);
        }
        //从入度为0的点开始出
        for(int i = 0; i < numCourses; i++) {
            if(in[i] == 0) {
                s.push(i);
            }
        }

        while(!s.isEmpty()) {
            int top = s.pop();
            for(int x : map.getOrDefault(top,new ArrayList<>())) {
                in[x]--;
                if(in[x] == 0) {
                    s.push(x);
                }
            }
        }
        for(int i = 0; i < numCourses; i++) {
            if(in[i] != 0) {
                return false;
            }
        }
        return true;
    }

    //前缀树的构建
    class Trie {

        class Node {
            Node[] node = new Node[27];
            boolean end;
        }
        Node root;
        public Trie() {
            root = new Node();
        }

        public void insert(String word) {
            Node cur = root;
            for(char ch : word.toCharArray()) {
                int i = ch - 'a';
                if(cur.node[i] == null) {
                    cur.node[i] = new Node();
                }
                cur = cur.node[i];
            }
            cur.end = true;
        }

        public boolean search(String word) {
            return find(word) == 2;
        }

        public boolean startsWith(String prefix) {
            return find(prefix) != 0;
        }
        private int find(String word) {
            Node cur = root;
            for(char ch : word.toCharArray()) {
                int i = ch - 'a';
                if(cur.node[i] == null) {
                    return 0;
                }
                cur = cur.node[i];
            }
            return cur.end ? 2 : 1;
        }
    }

    //二叉树的最近公共节点
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) {
            return null;
        }
        if(root == p || root == q) {
            return root;
        }
        TreeNode leftTree = lowestCommonAncestor(root.left,p,q);
        TreeNode rightTree = lowestCommonAncestor(root.right,p,q);
        if(leftTree != null && rightTree != null) {
            return root;
        }
        return leftTree == null ? rightTree : leftTree;
    }
}
